package experiment6;

import java.util.ArrayList;
import java.util.List;

/**
 * @author mazouri
 * @create 2021-12-02 12:04
 */
public class MFKnapsack {
    static int w = 5;
    static int[] weight = {2, 1, 3, 2};
    static int[] value = {12, 10, 20, 15};
    static int[][] memo = new int[weight.length + 1][w + 1];

    public static void main(String[] args) {
        //初始化备忘录数组，行0和列0的元素全部为0，其余元素全部为-1
        for (int i = 1; i < memo.length; i++) {
            for (int j = 1; j < memo[0].length; j++) {
                memo[i][j] = -1;
            }
        }

        System.out.println("最大价值为:" + knapsack(weight.length, w));
        System.out.println("构成最大价值的物品编号："+find());
    }

    /**
     * @param i 物品的数量
     * @param j 背包的承重量
     * @return 当前的最大值
     */
    private static int knapsack(int i, int j) {
        if (i == 0) return 0;

        if (memo[i][j] < 0) {
            //装不下该物品
            if (j < weight[i - 1]) memo[i][j] = knapsack(i - 1, j);
                //装得下，就比较(当前物品的价格+剩余空间的价值)和(没有该物品时的最大值)
            else memo[i][j] = Math.max(knapsack(i - 1, j), value[i - 1] + knapsack(i - 1, j - weight[i - 1]));
        }

        return memo[i][j];
    }

    private static List<Integer> find() {
        //具体物品编号
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = weight.length; i > 0; i--) {
            if (memo[i][w] > memo[i - 1][w]) {
                res.add(i);
                w = w-weight[i-1];
            }
        }
        return res;
    }
}
